package Greddy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 763.划分字母区间
 * 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
 * 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
 * 返回一个表示每个字符串片段的长度的列表。
 */
public class partitionLabels {
    /**
     * 一刷，思路基本一样，直接看二刷更清晰
     */
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<Integer>();
        char[] charArray = s.toCharArray();
        Map<Character, Integer> map = new HashMap();
        int left = 0;
        int right = 0;
        for (int i = 0; i < charArray.length; i++) {
            map.put(charArray[i], i);
        }
        for (int i = 0; i < charArray.length; i++) {
            right = Math.max(right, map.get(charArray[i]));
            if (i == right) {
                result.add(right - left + 1);
                left = right + 1;
            }
        }
        return result;
    }

    /**
     * 二刷
     */
    public List<Integer> partitionLabels2(String s) {
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), i);
        }
        int start = 0;
        int end = map.get(s.charAt(0));
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, map.get(s.charAt(i)));
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }


    /**
     * hot100一刷
     */
    public List<Integer> partitionLabels3(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), i);
        }
        List<Integer> res = new ArrayList<>();
        int start = 0;
        int end = map.get(s.charAt(0));
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, map.get(s.charAt(i)));
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}
